package top.hkyzf.study.leetcode.tree;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2022-2-23 15:41
 */
public class 二叉搜索树的最近公共祖先_235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return search(root, p, q);
    }

    TreeNode search(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        // 右子树
        if (root.val < p.val && root.val < q.val) {
            return search(root.right, p, q);
        }
        // 左子树
        if (root.val > p.val && root.val > q.val) {
            return search(root.left, p, q);
        }
        return root;
    }

    @Test
    public void testLowestCommonAncestor () {
        TreeNode node8 = new TreeNode(5);
        TreeNode node7 = new TreeNode(3);
        TreeNode node6 = new TreeNode(9);
        TreeNode node5 = new TreeNode(7);
        TreeNode node4 = new TreeNode(4, node7, node8);
        TreeNode node3 = new TreeNode(0);
        TreeNode node2 = new TreeNode(8, node5, node6);
        TreeNode node1 = new TreeNode(2, node3, node4);
        TreeNode root = new TreeNode(6, node1, node2);

        TreeNode p = new TreeNode(3);
        TreeNode q = new TreeNode(5);

        TreeNode treeNode = lowestCommonAncestor(root, p, q);
        System.out.println(treeNode);
    }
}
